Many different methods for compressing bit strings have been proposed in the past and the following United Kingdom and United States of America patent specifications are quoted as examples.
British Pat. No. 1,534,069 (IBM) `Translating Apparatus` PA0 British Pat. No. 1,328,061 (IBM) `Data Processing System` PA0 British Pat. No. 1,292,772 (IBM) `Code Conversion Apparatus` PA0 U.S. Pat. No. 3,717,851 (IBM) `Processing of Compacted Data` PA0 U.S. Pat. No. 3,694,813 (IBM) `Method of Achieving Data Compaction Utilizing Variable Length Dependent Coding Techniques` PA0 U.S. Pat. No. 3,883,847 (Bell Telephone Laboratores) `Uniform Decoding of Minimum Redundancy Codes`
The common characteristic of the prior art cited above is that the bit strings to be encoded are of variable length. This leads to the use of fairly complex algorithms or large tables to achieve compression of the strings. In the character graphic display system described in our copending U.S. patent application Ser. No. 189,526, filed Sept. 22, 1980 pictures to be displayed on a display device are made up of a plurality of rows of character cells. Each character cell is defined in a central processing unit and transmitted to the display device as a bit string. The processing power in the display controllers is not very large compared with the central processing unit and storage for decompression tables is limited if not non-existent. Consequently, any compression technique used on the bit strings would have to use only limited processing and preferably not require the use of tables. A characteristic of the character cell definitions is that if the rows of pel bits are divided into groups, then patterns of digits recur; in order to achieve a compression using limited processing the present invention makes use of this repetition.